class Solution
{
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        // 贪心思想，每次先把花销大的先切了
        // 将 horizontalCut 和 verticalCut 按从大到小排序
        sort(horizontalCut.begin(), horizontalCut.end(), greater<>());
        sort(verticalCut.begin(), verticalCut.end(), greater<>());
        int ans = 0;
        int i = 0, j = 0;
        int v = 1, h = 1;
        while(i < m - 1 || j < n - 1)
        {
            if((j == n - 1) || (i < m - 1 && horizontalCut[i] > verticalCut[j]))
            {
                // 每次在水平方向上切割时，如果此前列数为 v，那么此次的开销为 horizontalCut[i] * v
                ans += horizontalCut[i++] * v;
                h++;    // 然后行数 h 加一
            }
            else /**/
            {
                // 每次在垂直方向上切割时，如果此前行数为 h，那么此次的开销为 verticalCut[j] * h
                ans += verticalCut[j++] * h;    // 然后列数 v 加一
                v++;
            }
        }
        return ans;
    }
};